package com.bee.剑指offer;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。
 * 树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
 */
public class 二叉树的下一个结点 {

    private static List<TreeLinkNode> inList = new ArrayList<>();

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        TreeLinkNode valueNode = pNode;
        while (pNode.next != null) {
            pNode = pNode.next;
        }
        inRound(pNode);
        // 此时pNode为二叉树的头节点
        for (int i = 0; i < inList.size() ; i++) {
            if(valueNode.val == inList.get(i).val) {
                if(i == inList.size() - 1) {
                    return null;
                }
                return inList.get(i + 1);
            }
        }
        return null;
    }


    public static void inRound(TreeLinkNode pNode) {
        if(pNode == null) {
            return;
        }
        inRound(pNode.left);
        inList.add(pNode);
        inRound(pNode.right);
    }

    public static void main(String[] args) {

    }
}

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
